package ink.lovejinhu.swardToOffer;

import ink.lovejinhu.common.TreeNode;

import java.util.HashMap;

/**
 * @Author: jin
 * @Date: 2021/8/27 15:43
 * @Version: V1.0
 * @Slogan: Great people are not born great, but show their greatness in the process of growing up
 **/
public class Offer_007 {
    int[] preorder;
    HashMap<Integer, Integer> res = new HashMap<>();

    /**
     * 输入前序和中序，生成树
     * 前序找根    根左右
     * 中序找子树   左根右
     *
     * @param preorder
     * @param inorder
     * @return
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        //key:存具体的值，value存索引
        for (int i = 0; i < inorder.length; i++) {
            res.put(inorder[i], i);
        }

        return build(0, 0, inorder.length - 1);
    }

    public TreeNode build(int i, int left, int right) {
        if (left > right) return null;
        TreeNode root = new TreeNode(preorder[i]);
        Integer rootIndexInorder = res.get(preorder[i]);  //根在中序遍历中的索引
        //left,rootIndexInorder-1;   都是左子树
        //rootIndexInorder+1,right   都是右子树
        root.left = build(i + 1, left, rootIndexInorder - 1);
        root.right = build(i + (rootIndexInorder - 1 - left + 1) + 1, rootIndexInorder + 1, right);
        return root;
    }


}
